package 剑指专题.队列栈;


/*
 * Author：江松
 * Date：2023/3/27 10:20
 *
栈的压入弹出序列：输入序列并不是有顺序的
1，辅助栈模拟
 */

import java.util.Stack;

public class Main3 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer>stack=new Stack<>();
        int i=0,j=0;
        for(;i<popA.length;++i){
            while(stack.isEmpty()||(j<pushA.length&&popA[i]!=stack.peek())){
                stack.push(pushA[j++]);
            }
            if(stack.peek()==popA[i])stack.pop();
        }
        return stack.isEmpty();
    }


    public boolean IsPopOrderAns(int [] pushA,int [] popA) {
        int n = pushA.length;
        //辅助栈
        Stack<Integer> s = new Stack<>();
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for(int i = 0; i < n; i++){
            //入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.isEmpty() || s.peek() != popA[i])){
                s.push(pushA[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(s.peek() == popA[i])
                s.pop();
                //不匹配序列
            else
                return false;
        }
        return true;
    }
}
